package 题目集.贪心;

import org.junit.Test;

import java.util.Arrays;
import java.util.Collections;

/**
 * 给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。
 * 除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。
 * 给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。
 * https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign/
 */
public class ch08_你可以安排的最多任务数目 {
    int[] tasks;
    int[] workers;
    int pills;
    int strength;
    int maxTask;    //最多可以完成的任务数

    public void init(int[] tasks, int[] workers, int pills, int strength) {
        this.tasks = tasks;
        this.workers = workers;
        this.pills = pills;
        this.strength = strength;
        this.maxTask = Math.min(tasks.length, workers.length);
        Arrays.sort(tasks);
        Arrays.sort(workers);
    }

    /**
     * 二分+贪心
     */
    public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
        init(tasks, workers, pills, strength);
        int l = 0, r = maxTask;
        while (l <= r) {
            int m = l + r >> 1;
            if (check(m)) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (l <= maxTask && check(l)) {
            return l;
        }
        return r;
    }

    /**
     * 尝试完成数量为M的任务
     * 原先思路：
     *      1.找到工人中最牛的m个，和任务中最轻松的m个
     *      2.如果任务中，让能力最弱的功能做最轻松的任务。
     *      3.如果有一个任务使得工人吃药丸后（或没有药丸）依然无法完成，那么该数量的任务就无法完成
     * 问题点：
     *      在原先的第二步中存在问题，任务可能会和你田忌赛马，把你药丸骗走。如用例：[5,5,8], [4,6,6], 1, 5。
     * 修改后的暴力思路：
     *      让工人中最弱的尝试去做最难的任务，如果就找轻松一点的任务，以此往复.
     *      如果完成不了一个任务，就尝试吃药再跑一轮，如果还是无法完成，返回false。
     *      如果完成了一个任务，就继续让下一个工人尝试。
     */
    public boolean check1(int m) {    //尝试完成数量为M的任务
        int pills = this.pills;
        boolean[] vis = new boolean[m];
        for (int i = 0; i < m; i++) {
            int worker = workers[workers.length - m + i];
            int j = m - 1;
            for (; j >= 0; j--) {   //找到刚好能做的任务
                if (vis[j]) {
                    continue;
                }
                if (tasks[j] <= worker) {
                    vis[j] = true;
                    break;
                }
            }
            if (j < 0) {    //如果没有找到刚好能做的任务
                if (pills == 0) {
                    return false;
                }
                pills--;
                worker += strength;
                j = m - 1;
                for (; j >= 0; j--) {   //吃药后再次尝试
                    if (vis[j]) {
                        continue;
                    }
                    if (tasks[j] <= worker) {
                        vis[j] = true;
                        break;
                    }
                }
                if (j < 0) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 尝试完成数量为M的任务
     * 优化：
     *      在原有的错误思路中，核心的问题在于，药可能会以田忌赛马的方式骗走，导致后面的大任务无法做。
     *      虽然方式1可以解决这个问题，但是在找到最轻松的任务时，会有很多重复的计算。
     * 优化思路：
     *      1.先找到工人中最弱的m个，和任务中最轻松的m个
     *      2.解锁当前工人能做的任务有哪些，将解锁的任务放入队列中
     *      3.如果当前队列中还有任务，就尝试让工人取走最简单的任务。（有可能是前人通过吃药解锁的）
     *      4.如果队列中没有任务，或则无法取走最简单的任务
     *          则吃药，再次解锁任务，然后取走最难的任务。（因为是自己解锁的，所以一定能取走）
     *          如果吃药后还是无法取走任何一个任务，或者没有药，返回false
     */
    public boolean check(int m) {
        int pills = this.pills;
        int n = m + 1;
        int[] deque = new int[n];
        int l = 0, r = 0;
        for (int i = 0, j = 0; j < m; j++) {
            int worker = workers[workers.length - m + j];
            while (i < m && worker >= tasks[i]) {   //如果还有任务，则尝试解锁
                deque[r] = i++;
                r = (r + 1) % n;
            }
            if (l == r || worker < tasks[deque[l]]) {   //如果无法解锁任务，或者无法取走最简单的任务
                if (pills-- == 0) {
                    return false;
                }
                worker += strength;
                while (i < m && worker >= tasks[i]) {   //吃药后再次尝试解锁
                    deque[r] = i++;
                    r = (r + 1) % n;
                }
                if (l == r) {
                    return false;
                }
                r = (r + n - 1) % n;        //取走最难的任务
            }else {
                l = (l + 1) % n;            //取走最简单的任务
            }
        }
        return true;
    }

    @Test
    public void test() {
        System.out.println(maxTaskAssign(new int[]{10, 15, 30}, new int[]{0, 10, 10, 10, 10}, 3, 10));
    }
}
